
//
// CS251 Data Structures
// Hash Table
//

#include <assert.h>
#include <stdlib.h>
#include <string.h>

// Each hash entry stores a key, object pair
template <typename Data>
struct HashTableTemplateEntry {
	const char * _key;
	Data _data;
	HashTableTemplateEntry * _next;
};

// This is a Hash table that maps string keys to objects of type Data
template <typename Data>
class HashTableTemplate {
public:
	// Number of buckets
	enum { TableSize = 2039};

	// Array of the hash buckets.
	HashTableTemplateEntry<Data> **_buckets;

	// Obtain the hash code of a key
	int hash(const char * key);

public:
	HashTableTemplate();

	// Add a record to the hash table. Returns true if key already exists.
	// Substitute content if key already exists.
	bool insertItem( const char * key, Data data);

	// Find a key in the dictionary and place in "data" the corresponding record
	// Returns false if key is does not exist
	bool find( const char * key, Data * data);

	// Removes an element in the hash table. Return false if key does not exist.
	bool removeElement(const char * key);

	// Returns the data that corresponds to this index.
	// Data is initialized to 0s if the entry does not exist
	Data operator[] (const char * &key);
};

template <typename Data>
int HashTableTemplate<Data>::hash(const char * key)
{
	int h = 0;
	const char * p = key;
	while (*p) {
		h += *p;
		p++;
	}
	return h % TableSize;
}

template <typename Data>
HashTableTemplate<Data>::HashTableTemplate()
{
	_buckets = (HashTableTemplateEntry<Data>**)malloc(TableSize*sizeof(HashTableTemplateEntry<Data>));
	for (int idx = 0; idx < TableSize; idx++)
		_buckets[idx] = NULL;
}

template <typename Data>
bool HashTableTemplate<Data>::insertItem( const char * key, Data data)
{
	int h = hash(key);
	HashTableTemplateEntry<Data> *node = _buckets[h];
	HashTableTemplateEntry<Data> *prev = NULL;
	while (node != NULL) {
		if (!strcmp(node->_key, key)) {
			node->_data = data;
			return true;
		}
		prev = node;
		node = node->_next;
	}
	node = new HashTableTemplateEntry<Data>();
	node->_key = strdup(key);
	node->_data = data;
	node->_next = NULL;
	if (prev == NULL)
		_buckets[h] = node;
	else
		prev->_next = node;
	return false;
}

template <typename Data>
bool HashTableTemplate<Data>::find( const char * key, Data * data)
{
	int h = hash(key);
	HashTableTemplateEntry<Data> *node = _buckets[h];
	if (node == NULL)
		return false;
	while (node != NULL) {
		if (!strcmp(node->_key, key))
			break;
		node = node->_next;
	}
	if (node == NULL) {
		data = NULL;
		return false;
	}
	if (data != NULL)
		*data = node->_data;
	return true;
}

template <typename Data>
Data HashTableTemplate<Data>::operator[] (const char * &key) {
	return _buckets[hash(key)]->_data;
}

template <typename Data>
bool HashTableTemplate<Data>::removeElement(const char * key)
{
	int h = hash(key);
	HashTableTemplateEntry<Data> *temp, *prev;
	if (find(key, NULL)) {
		temp = _buckets[h];
		if (!strcmp(temp->_key, key)) {
			_buckets[h] = NULL;
			return true;
		}
		while (temp != NULL && !strcmp(temp->_key, key)) {
			prev = temp;
			temp = temp->_next;
		}
		if (prev != NULL && !strcmp(prev->_key, key)) {
			if (prev != NULL && temp != NULL)
				prev->_next = temp->_next;
			delete prev;
		}
		return true;
	}
	return false;
}

template <typename Data>
class HashTableTemplateIterator {
	int _currentBucket;
	HashTableTemplateEntry<Data> *_currentEntry;
	HashTableTemplate<Data> * _hashTable;
	bool validKey;
public:
	HashTableTemplateIterator(HashTableTemplate<Data> * hashTable);
	bool next(const char * & key, Data & data);
};

template <typename Data>
HashTableTemplateIterator<Data>::HashTableTemplateIterator(HashTableTemplate<Data> * hashTable)
{
	_hashTable = hashTable;
	_currentEntry = NULL;
	_currentBucket = -1;
	validKey = false;
}

template <typename Data>
bool HashTableTemplateIterator<Data>::next(const char * & key, Data & data)
{
	if (_currentBucket == -1) {
		if (!_hashTable->find(key, NULL))
			_currentBucket = 0;
		else {
			_currentBucket = _hashTable->hash(key);
			validKey = true;
		}
	}
	if (_currentEntry == NULL && _currentBucket != _hashTable->TableSize)
		_currentEntry = _hashTable->_buckets[_currentBucket];
	if (validKey) {
		if (_currentEntry->_next != NULL) {
			data = _currentEntry->_data;
			_currentEntry = _currentEntry->_next;
			return true;
		}
		else {
			data = _currentEntry->_data;
			return false;
		}
	}
	else {
		if (_currentEntry == NULL && _currentBucket + 1 != _hashTable->TableSize) {
			while (_currentEntry == NULL) {
				_currentBucket++;
				_currentEntry = _hashTable->_buckets[_currentBucket];
			}
			data = _currentEntry->_data;
			return true;
		}
		if (_currentEntry->_next != NULL) {
			data = _currentEntry->_data;
			_currentEntry = _currentEntry->_next;
			return true;
		}
		else {
			_currentBucket++;
			_currentEntry = _hashTable->_buckets[_currentBucket];
			while (_currentEntry == NULL) {
				_currentBucket++;
				_currentEntry = _hashTable->_buckets[_currentBucket];
			}
		}
	}
	return false;
}
